package sort.leetcode_912;

public class CountSort {
    public static void main(String[] args) {
        int[] nums = new int[] {-10,7,-2,3,4,9,2,-3,-1,0};
        sortArray(nums);
    }
    public static int[] sortArray(int[] nums) {
        if(nums.length == 1){
            return nums;
        }
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int value : nums){
            if(value > max){
                max = value;
            }
            if(value < min){
                min = value;
            }
        }
        int len = max - min + 1;
        int[] count = new int[len];
        //以最小值作为偏移量，将负数转换成正数
        for(int i = 0; i < nums.length; i++){
            count[nums[i] - min]++;
        }
        int index = 0;
        for(int i = 0; i < count.length; i++){
            while(count[i] > 0){
                nums[index++] = i + min;
                count[i]--;
            }
        }
        return nums;
    }
}
